Problem statement: zenit17kkl

Levely KNIGHTS

Počet bodov: 45, časový limit: 1000ms

KNIGHTS je logická počítačová hra. Má veľmi jednoduché pravidlá. Hráč dostane obdĺžnikovú šachovnicu. Na niektorých políčkach sú steny, niektoré sú prázdne a niektoré obsahujú šachového koňa jednej z troch farieb. Niektoré nezablokované políčka sú navyše zafarbené jednou z týchto farieb. Level je vyriešený, ak je na každom zafarbenom políčku kôň danej farby. Jediné, čo hráč môže urobiť, je zobrať ľubovoľného koňa a jedným ťahom (šachového koňa – o jedno políčko v jednom smere, o dve políčka v kolmom smere) ho presunúť na prázdne políčko.

V tejto úlohe budete testovať nové návrhy levelov KNIGHTS. Čím viac ťahov treba spraviť na vyriešenie levelu, tým je ťažší. Pre dané začiatočné rozostavenie levelu povedzte pre každý návrh konečného rozostavenia, koľko najmenej ťahov treba na jeho vyriešenie.

Vstup a výstup

V prvom riadku sú dve celé čísla \(1 \leq r,s \leq 23\) – počet riadkov a stĺpcov hracej plochy. Nasleduje \(r\) riadkov po \(s\) znakoch, reprezentujúcich začiatočné rozostavenie levelu. # je stena, . je voľné políčko a RBY sú kone danej farby (Red, Blue, Yellow). Počet políčok, ktoré nie sú stenami, je najviac 12.

Nasleduje číslo \(1 \leq q \leq 75\,000\) – počet navrhovaných zafarbení políčok. Vo všetkých vstupoch platí \(q * r * s \leq 10^6\).

Nasleduje \(q\) popisov hracej plochy v rovnakom horeuvedenom formáte. Všetky navrhované konečné rozostavenia majú rovnakú veľkosť ako začiatočné, majú steny na rovnakých miestach a počet koňov každej farby je rovnaký ako v začiatočnom rozostavení.

Po každom rozostavení nasleduje jeden prázdny riadok.

Pre každé navrhované konečné rozostavenie vypíšte najmenší počet ťahov potrebných na jeho dosiahnutie. Ak sa nejaké rozostavenie nedá vôbec dosiahnuť, vypíšte \(-1\).

Sú štyri sady vstupov. Hodnoty na vstupe sú na nich zhora obmedzené nasledovne:

Príklady

Input:

2 2
#R
.B

2
#R
.B

#B
.R

Output:

0
-1

Input:

3 4
#BYY
..R#
.BYR

4
#BYY
..R#
.BYR

#.YY
..R#
BBYR

#Y.Y
B.R#
.YRB

#..R
YYB#
YBR.

Output:

0
1
19
-1